# 5. 最长回文子串
# https://leetcode-cn.com/problems/longest-palindromic-substring/
# 给你一个字符串 s，找到 s 中最长的回文子串。
#
#
#
# 示例 1：
#
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。
# 示例 2：
#
# 输入：s = "cbbd"
# 输出："bb"
# 示例 3：
#
# 输入：s = "a"
# 输出："a"
# 示例 4：
#
# 输入：s = "ac"
# 输出："a"
#
#
# 提示：
#
# 1 <= s.length <= 1000
# s 仅由数字和英文字母（大写和/或小写）组成
# -----
# 讨论:
# - 用动态规划, 但怎么着都想不到状态转移方式
#         d[i][j] = d[i-1][j+1] and s[i] == s[j]
#         d[i][j]这里为状态, 不再是最长公共字串类的了, 为True表示s[i:(j+1)]为回文
# - python slice
# s[::-1]

# 14:00
class Solution:
    @staticmethod
    def max_substr(s1: str, s2: str) -> str:
        """
        最长公共字串
        :param s1:
        :param s2:
        :return:
        """
        d = {}
        for i in range(len(s1)):
            for j in range(len(s2)):
                if s1[i] != s2[j]:
                    continue
                if (i - 1, j - 1) not in d:
                    d[(i, j)] = s1[i]
                else:
                    d[(i, j)] = d[(i - 1, j - 1)] + s1[i]
        return max(d.values(), key=len)

    def longestPalindrome(self, s: str) -> str:
        """
        用动态规划, 但怎么着都想不到状态转移方式
        d[i][j] = d[i-1][j+1] and s[i] == s[j]
        d[i][j]这里为状态, 不再是最长公共字串类的了, 为True表示s[i:(j+1)]为回文
        """
        # 表示s[i:j]为回文
        d = set()
        for l in range(1, len(s) + 1):
            for i in range(0, len(s)):
                j = i + l
                if j > len(s):
                    break
                if s[i] == s[j - 1]:
                    if i + 1 >= j - 1 or (i + 1, j - 1) in d:
                        d.add((i, j))
        if len(d):
            st, ed = max(d, key=lambda x: x[1] - x[0])
            return s[st: ed]
        else:
            return s[0] if len(s) else ''

    def longestPalindrome1(self, s: str) -> str:
        """
        用动态规划, 但怎么着都想不到状态转移方式
        d[i][j] = d[i-1][j+1] and s[i] == s[j]
        d[i][j]这里为状态, 不再是最长公共字串类的了, 为True表示s[i:(j+1)]为回文
        """
        # 表示s[i:j]为回文
        n = len(s)
        d = [[False] * (n + 1) for _ in range(n)]
        for i in range(n):
            d[i][i+1] = True

        for l in range(1, len(s) + 1):
            for i in range(0, len(s)):
                j = i + l
                if j > len(s):
                    break
                if s[i] == s[j - 1]:
                    if i + 1 >= j - 1 or d[i + 1][j - 1]:
                        d[i][j] = True
        ss = []
        for i in range(n):
            for j in range(n + 1):
                if d[i][j]:
                    ss.append((i, j))
        st, ed = max(ss, key=lambda x: x[1] - x[0])
        return s[st: ed]

    def longestPalindrome2(self, s: str) -> str:
        """
        'cbabad' vs 'dababc' => 改为最长公共字串问题, 这种解法漏掉了: aacabdkacaa的情况会认为aaca是回文
        'dababc'
        :param s:
        :return:
        """
        return Solution.max_substr(s, s[::-1])


solution = Solution()
assert solution.longestPalindrome('cbabad') == 'bab'
assert solution.longestPalindrome('cbbd') == 'bb'
assert solution.longestPalindrome('a') == 'a'
assert solution.longestPalindrome('ac') == 'a'
assert solution.longestPalindrome("aacabdkacaa") == "aca"
assert solution.longestPalindrome("aaaa") == "aaaa"
assert solution.longestPalindrome("abcba") == "abcba"


